{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number Of Ways To Reconstruct A Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重构一棵树的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>pairs</code> ，其中 <code>pairs[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> ，并且满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>pairs</code> 中没有重复元素</li>\n",
    "\t<li><code>x<sub>i</sub> < y<sub>i</sub></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>令 <code>ways</code> 为满足下面条件的有根树的方案数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树所包含的所有节点值都在 <code>pairs</code> 中。</li>\n",
    "\t<li>一个数对 <code>[x<sub>i</sub>, y<sub>i</sub>]</code> 出现在 <code>pairs</code> 中 <strong>当且仅当</strong><strong> </strong><code>x<sub>i</sub></code> 是 <code>y<sub>i</sub></code> 的祖先或者 <code>y<sub>i</sub></code> 是 <code>x<sub>i</sub></code><sub> </sub>的祖先。</li>\n",
    "\t<li><strong>注意：</strong>构造出来的树不一定是二叉树。</li>\n",
    "</ul>\n",
    "\n",
    "<p>两棵树被视为不同的方案当存在至少一个节点在两棵树中有不同的父节点。</p>\n",
    "\n",
    "<p>请你返回：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>ways == 0</code> ，返回 <code>0</code> 。</li>\n",
    "\t<li>如果 <code>ways == 1</code> ，返回 <code>1</code> 。</li>\n",
    "\t<li>如果 <code>ways > 1</code> ，返回 <code>2</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一棵 <strong>有根树</strong> 指的是只有一个根节点的树，所有边都是从根往外的方向。</p>\n",
    "\n",
    "<p>我们称从根到一个节点路径上的任意一个节点（除去节点本身）都是该节点的 <strong>祖先</strong> 。根节点没有祖先。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/09/trees2.png\" style=\"width: 208px; height: 221px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>pairs = [[1,2],[2,3]]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>如上图所示，有且只有一个符合规定的有根树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/09/tree.png\" style=\"width: 234px; height: 241px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>pairs = [[1,2],[2,3],[1,3]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>有多个符合规定的有根树，其中三个如上图所示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pairs = [[1,2],[2,3],[2,4],[1,5]]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>没有符合规定的有根树。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= pairs.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= x<sub>i </sub>< y<sub>i</sub> <= 500</code></li>\n",
    "\t<li><code>pairs</code> 中的元素互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-reconstruct-a-tree](https://leetcode.cn/problems/number-of-ways-to-reconstruct-a-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-reconstruct-a-tree](https://leetcode.cn/problems/number-of-ways-to-reconstruct-a-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,3]]', '[[1,2],[2,3],[1,3]]', '[[1,2],[2,3],[2,4],[1,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        cnt, mx = Counter(), 0\n",
    "        hh = defaultdict(int)\n",
    "        for u, v in pairs:\n",
    "            cnt[u] += 1\n",
    "            cnt[v] += 1\n",
    "            hh[u] |= 1 << v\n",
    "            hh[v] |= 1 << u\n",
    "            hh[u] |= 1 << u\n",
    "            hh[v] |= 1 << v\n",
    "            mx = max(mx, u, v)\n",
    "        n = len(cnt)\n",
    "        if len(pairs) == n * (n - 1) // 2:\n",
    "            # 单链，那就肯定有多种方案\n",
    "            return 2\n",
    "        st = {i for i in cnt if cnt[i] == n - 1}\n",
    "        m = len(st)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        f = list(range(mx + 1))\n",
    "        dep = [0] * (mx + 1)\n",
    "        sz = [1] * (mx + 1)\n",
    "        def find(i):\n",
    "            if i != f[i]:\n",
    "                f[i] = find(f[i])\n",
    "            return f[i]\n",
    "        def join(i, j):\n",
    "            fi, fj = find(i), find(j)\n",
    "            if fi == fj:\n",
    "                return\n",
    "            if fi > fj:\n",
    "                fi, fj = fj, fi\n",
    "            f[fj] = fi\n",
    "            sz[fi] += sz[fj]\n",
    "\n",
    "        for u, v in pairs:\n",
    "            if cnt[u] == cnt[v]:\n",
    "                if hh[u] != hh[v]:\n",
    "                    return 0\n",
    "                join(u, v)\n",
    "\n",
    "        g = defaultdict(set)\n",
    "        ii = Counter()\n",
    "        for u, v in pairs:\n",
    "            if cnt[u] == cnt[v]:\n",
    "                continue\n",
    "            a, b = find(u), find(v)\n",
    "            if cnt[u] > cnt[v]:\n",
    "                a, b = b, a\n",
    "            if a not in g[b]:\n",
    "                g[b].add(a)\n",
    "                ii[a] += 1\n",
    "        ts, i = [find(list(st)[0])], 0\n",
    "        dp = Counter()\n",
    "        p = {}\n",
    "        while i < len(ts):\n",
    "            dp[ts[i]] += sz[ts[i]] - 1\n",
    "            for j in g[ts[i]]:\n",
    "                ii[j] -= 1\n",
    "                if ii[j] == 0:\n",
    "                    ts.append(j)\n",
    "                    dp[j] = dp[ts[i]] + 1\n",
    "                    p[j] = ts[i]\n",
    "            i += 1\n",
    "        gc = len({find(i) for i in cnt})\n",
    "        if gc != len(ts):\n",
    "            return 0\n",
    "        dp2 = Counter()\n",
    "        for v in ts[::-1]:\n",
    "            if v in p:\n",
    "                u = p[v]\n",
    "                dp[u] += dp2[v] + sz[v]\n",
    "                dp2[u] += dp2[v] + sz[v]\n",
    "        for i in cnt:\n",
    "            if cnt[i] != dp[find(i)]:\n",
    "                return 0\n",
    "                \n",
    "        return 1 if len(cnt) == len(dp) else 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs):\n",
    "        N = 510\n",
    "        cnts = [0] * N\n",
    "        fa = [0] * N\n",
    "        g = [[False] * N for _ in range(N)]\n",
    "        \n",
    "        m = len(pairs)\n",
    "        seen = set()\n",
    "        \n",
    "        for p in pairs:\n",
    "            a, b = p[0], p[1]\n",
    "            g[a][b] = g[b][a] = True\n",
    "            cnts[a] += 1\n",
    "            cnts[b] += 1\n",
    "            seen.add(a)\n",
    "            seen.add(b)\n",
    "        \n",
    "        arr = list(seen)\n",
    "        arr.sort(key=lambda x: cnts[x], reverse=True)\n",
    "        \n",
    "        n = len(arr)\n",
    "        root = arr[0]\n",
    "        \n",
    "        if m < n - 1:\n",
    "            return 0\n",
    "        \n",
    "        fa[root] = -1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            a = arr[i]\n",
    "            ok = False\n",
    "            \n",
    "            for j in range(i - 1, -1, -1):\n",
    "                b = arr[j]\n",
    "                \n",
    "                if g[a][b]:\n",
    "                    fa[a] = b\n",
    "                    ok = True\n",
    "                    break\n",
    "            \n",
    "            if not ok:\n",
    "                return 0\n",
    "        \n",
    "        c = 0\n",
    "        ans = 1\n",
    "        \n",
    "        for i in seen:\n",
    "            j = i\n",
    "            \n",
    "            while fa[j] != -1:\n",
    "                if not g[i][fa[j]]:\n",
    "                    return 0\n",
    "                \n",
    "                if cnts[i] == cnts[fa[j]]:\n",
    "                    ans = 2\n",
    "                \n",
    "                c += 1\n",
    "                j = fa[j]\n",
    "        \n",
    "        return 0 if c < m else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs):\n",
    "        N = 510\n",
    "        cnts = [0] * N\n",
    "        fa = [0] * N\n",
    "        g = [[False] * N for _ in range(N)]\n",
    "        \n",
    "        m = len(pairs)\n",
    "        nodes_set = set()\n",
    "        \n",
    "        for p in pairs:\n",
    "            a, b = p\n",
    "            g[a][b] = g[b][a] = True\n",
    "            cnts[a] += 1\n",
    "            cnts[b] += 1\n",
    "            nodes_set.add(a)\n",
    "            nodes_set.add(b)\n",
    "        \n",
    "        nodes_list = list(nodes_set)\n",
    "        nodes_list.sort(key=lambda x: cnts[x], reverse=True)\n",
    "        \n",
    "        n = len(nodes_list)\n",
    "        root = nodes_list[0]\n",
    "        \n",
    "        if m < n - 1:\n",
    "            return 0\n",
    "        \n",
    "        fa[root] = -1\n",
    "        for i in range(1, n):\n",
    "            a = nodes_list[i]\n",
    "            ok = False\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                b = nodes_list[j]\n",
    "                if g[a][b]:\n",
    "                    fa[a] = b\n",
    "                    ok = True\n",
    "                    break\n",
    "            if not ok:\n",
    "                return 0\n",
    "        \n",
    "        c = 0\n",
    "        ans = 1\n",
    "        \n",
    "        for i in nodes_set:\n",
    "            j = i\n",
    "            while fa[j] != -1:\n",
    "                if not g[i][fa[j]]:\n",
    "                    return 0\n",
    "                if cnts[i] == cnts[fa[j]]:\n",
    "                    ans = 2\n",
    "                c += 1\n",
    "                j = fa[j]\n",
    "        \n",
    "        return 0 if c < m else ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs):\n",
    "        N = 510\n",
    "        cnts = [0] * N\n",
    "        fa = [0] * N\n",
    "        g = [[False] * N for _ in range(N)]\n",
    "        \n",
    "        m = len(pairs)\n",
    "        nodes_set = set()\n",
    "        \n",
    "        for p in pairs:\n",
    "            a, b = p\n",
    "            g[a][b] = g[b][a] = True\n",
    "            cnts[a] += 1\n",
    "            cnts[b] += 1\n",
    "            nodes_set.add(a)\n",
    "            nodes_set.add(b)\n",
    "        \n",
    "        nodes_list = list(nodes_set)\n",
    "        nodes_list.sort(key=lambda x: cnts[x], reverse=True)\n",
    "        \n",
    "        n = len(nodes_list)\n",
    "        root = nodes_list[0]\n",
    "        \n",
    "        if m < n - 1:\n",
    "            return 0\n",
    "        \n",
    "        fa[root] = -1\n",
    "        for i in range(1, n):\n",
    "            a = nodes_list[i]\n",
    "            ok = False\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                b = nodes_list[j]\n",
    "                if g[a][b]:\n",
    "                    fa[a] = b\n",
    "                    ok = True\n",
    "                    break\n",
    "            if not ok:\n",
    "                return 0\n",
    "        \n",
    "        c = 0\n",
    "        ans = 1\n",
    "        \n",
    "        for i in nodes_set:\n",
    "            j = i\n",
    "            while fa[j] != -1:\n",
    "                if not g[i][fa[j]]:\n",
    "                    return 0\n",
    "                if cnts[i] == cnts[fa[j]]:\n",
    "                    ans = 2\n",
    "                c += 1\n",
    "                j = fa[j]\n",
    "        \n",
    "        return 0 if c < m else ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        gp = dict()\n",
    "        for p in pairs:\n",
    "            if gp.get(p[0],-1)!=-1:\n",
    "                gp[p[0]].append(p[1]) \n",
    "            else:\n",
    "                 gp[p[0]] = [p[1]]\n",
    "            if gp.get(p[1],-1)!=-1:\n",
    "                gp[p[1]].append(p[0]) \n",
    "            else:\n",
    "                 gp[p[1]] = [p[0]]\n",
    "        root = -1\n",
    "        for k,v in gp.items():\n",
    "            if len(v)==len(gp)-1:\n",
    "                root = k\n",
    "                break\n",
    "        if root==-1:\n",
    "            return 0\n",
    "        res = 1\n",
    "        for k,v in gp.items():\n",
    "            if k==root:\n",
    "                continue\n",
    "            currDegree = len(v)\n",
    "            p = -1\n",
    "            pdegree = 2**31-1\n",
    "            for n in v:\n",
    "                if currDegree<=len(gp[n])<pdegree:\n",
    "                    p = n\n",
    "                    pdegree = len(gp[n])\n",
    "            if p==-1 or any(neighbour != p and neighbour not in gp[p] for neighbour in v):\n",
    "                return 0\n",
    "            if pdegree==currDegree:\n",
    "                res = 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        ans=1\n",
    "        c=Counter()\n",
    "        g=defaultdict(list)\n",
    "        for u,v in pairs:\n",
    "            c[u]+=1\n",
    "            c[v]+=1\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        n=len(c)\n",
    "        res=sorted(c.keys(),key=lambda x: -c[x])#按照关系数排序\n",
    "        for u,v in pairs:\n",
    "            if c[u]==c[v]:\n",
    "                ans=2\n",
    "        par={}\n",
    "        if c[res[0]]!=n-1:#判断根的关系数是否满足条件\n",
    "            ans=0\n",
    "        else:\n",
    "            for i in res:\n",
    "                par[i]=res[0]#将所有节点先挂在根节点下\n",
    "            f=True\n",
    "            vis={res[0]}\n",
    "            for i in range(1,n):\n",
    "                for v in g[res[i]]:\n",
    "                    if v not in vis:\n",
    "                        if par[v]!=par[res[i]]:#判断是否能够更新\n",
    "                            ans=0\n",
    "                            f=False\n",
    "                            break\n",
    "                        par[v]=res[i]#将v挂到当前节点res[i]下\n",
    "                if not f:\n",
    "                    break\n",
    "                vis.add(res[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        ans = 1\n",
    "        cnt = Counter()\n",
    "        g = defaultdict(list)\n",
    "        for u, v in pairs:\n",
    "            cnt[u] += 1\n",
    "            cnt[v] += 1\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        n = len(cnt)\n",
    "        for u, v in pairs:\n",
    "            if cnt[u] == cnt[v]:\n",
    "                ans = 2\n",
    "        res = sorted(cnt.keys(), key=lambda x: -cnt[x])\n",
    "        par = {}\n",
    "        if cnt[res[0]] != n - 1:\n",
    "            ans = 0\n",
    "        else:\n",
    "            for i in res:\n",
    "                par[i] = res[0]\n",
    "            ok = True\n",
    "            vis = {res[0]}\n",
    "            for i in range(1, n):\n",
    "                for v in g[res[i]]:\n",
    "                    if v not in vis:\n",
    "                        if par[v] != par[res[i]]:\n",
    "                            ans = 0\n",
    "                            ok = False\n",
    "                            break\n",
    "                        par[v] = res[i]\n",
    "                if not ok:\n",
    "                    break\n",
    "                vis.add(res[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        ans = 1 \n",
    "        c = Counter()\n",
    "        g = defaultdict(list)\n",
    "        for u, v in pairs:\n",
    "            c[u] += 1\n",
    "            c[v] += 1\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        n = len(c)\n",
    "        res = sorted(c.keys(), key = lambda x: -c[x])\n",
    "        for u, v in pairs:\n",
    "            if c[u] == c[v]:\n",
    "                ans = 2\n",
    "        par = {}\n",
    "        if c[res[0]] != n - 1:\n",
    "            ans = 0\n",
    "        else:\n",
    "            for i in res:\n",
    "                par[i] = res[0]\n",
    "            f = True\n",
    "            vis = {res[0]}\n",
    "            for i in range(1, n):\n",
    "                for v in g[res[i]]:\n",
    "                    if v not in vis:\n",
    "                        if par[v] != par[res[i]]:\n",
    "                            ans = 0\n",
    "                            f = False\n",
    "                            break\n",
    "                        par[v] = res[i]\n",
    "                if not f:\n",
    "                    break\n",
    "                vis.add(res[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        ans=1\n",
    "        c=Counter()\n",
    "        g=defaultdict(list)\n",
    "        for u,v in pairs:\n",
    "            c[u]+=1\n",
    "            c[v]+=1\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        n=len(c)\n",
    "        res=sorted(c.keys(),key=lambda x: -c[x])#按照关系数排序\n",
    "        for u,v in pairs:\n",
    "            if c[u]==c[v]:\n",
    "                ans=2\n",
    "        par={}\n",
    "        if c[res[0]]!=n-1:#判断根的关系数是否满足条件\n",
    "            ans=0\n",
    "        else:\n",
    "            for i in res:\n",
    "                par[i]=res[0]#将所有节点先挂在根节点下\n",
    "            f=True\n",
    "            vis={res[0]}\n",
    "            for i in range(1,n):\n",
    "                for v in g[res[i]]:\n",
    "                    if v not in vis:\n",
    "                        if par[v]!=par[res[i]]:#判断是否能够更新\n",
    "                            ans=0\n",
    "                            f=False\n",
    "                            break\n",
    "                        par[v]=res[i]#将v挂到当前节点res[i]下\n",
    "                if not f:\n",
    "                    break\n",
    "                vis.add(res[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        ans = 1\n",
    "        c = Counter()\n",
    "        g = defaultdict(list)\n",
    "        \n",
    "        # 统计每个节点出现的次数，并建立图的连接\n",
    "        for u, v in pairs:\n",
    "            c[u] += 1\n",
    "            c[v] += 1\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        # 对所有的节点按照它们出现的次数进行排序\n",
    "        res = sorted(c.keys(), key=lambda x: -c[x])\n",
    "        \n",
    "        # 判断是否有多个方案\n",
    "        for u, v in pairs:\n",
    "            if c[u] == c[v]:\n",
    "                ans = 2\n",
    "                \n",
    "        par = {}\n",
    "        \n",
    "        # 判断是否有有效的方案\n",
    "        if c[res[0]] != len(res) - 1:\n",
    "            ans = 0\n",
    "        else:\n",
    "            for i in res:\n",
    "                par[i] = res[0]\n",
    "                \n",
    "            f = True\n",
    "            vis = {res[0]}\n",
    "            \n",
    "            for i in range(1, len(res)):\n",
    "                for v in g[res[i]]:\n",
    "                    if v not in vis:\n",
    "                        if par[v] != par[res[i]]:\n",
    "                            ans = 0\n",
    "                            f = False\n",
    "                            break\n",
    "                        par[v] = res[i]\n",
    "                if not f:\n",
    "                    break\n",
    "                vis.add(res[i])\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        d = defaultdict(set)\n",
    "        for i, j in pairs:\n",
    "            d[i].add(j)\n",
    "            d[j].add(i)\n",
    "\n",
    "        # 检测是否有根节点\n",
    "        root = -1\n",
    "        for i, neighbors in d.items():\n",
    "            if len(neighbors) == len(d) - 1:\n",
    "                root = i\n",
    "                break\n",
    "        if root == -1:\n",
    "            return 0\n",
    "        ans = 1\n",
    "        for node, neighbors in d.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            nowDegree = len(neighbors)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 寻找node的父节点\n",
    "            for neighbor in neighbors:\n",
    "                if nowDegree <= len(d[neighbor]) < parentDegree:\n",
    "                    parent = neighbor\n",
    "                    parentDegree = len(d[neighbor])\n",
    "            if parent == -1 or any(neighbor != parent and neighbor not in d[parent] for neighbor in neighbors):\n",
    "                return 0\n",
    "            if parentDegree == nowDegree:\n",
    "                ans = 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        # 如果 a 是 b 的祖先节点，那么 degree[a] >= degree[b]\n",
    "        g = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        \n",
    "        # 根节点的度最好确定\n",
    "        root = -1\n",
    "        for x, neighbours in g.items():\n",
    "            if len(neighbours) == len(g) - 1:\n",
    "                root = x\n",
    "                break\n",
    "        if root == -1: # 没有符合条件的根节点\n",
    "            return 0\n",
    "        \n",
    "        ans = 1\n",
    "        for node, neighbours in g.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            currDegree = len(neighbours)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 根据 degree 的大小找到 node 的父节点 parent\n",
    "            for y in neighbours:\n",
    "                if currDegree <= len(g[y]) < parentDegree:\n",
    "                    parent = y\n",
    "                    parentDegree = len(g[y])\n",
    "            # 检测 neighbours 是否为 g[parent] 的子集\n",
    "            if parent == -1 or any(y != parent and y not in g[parent] for y in neighbours):\n",
    "                return 0\n",
    "\n",
    "            if parentDegree == currDegree:\n",
    "                ans = 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "\n",
    "        # 检测是否存在根节点\n",
    "        root = next((node for node, neighbours in adj.items() if len(neighbours) == len(adj) - 1), -1)\n",
    "        if root == -1:\n",
    "            return 0\n",
    "\n",
    "        ans = 1\n",
    "        for node, neighbours in adj.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            currDegree = len(neighbours)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 根据 degree 的大小找到 node 的父节点 parent\n",
    "            for neighbour in neighbours:\n",
    "                if currDegree <= len(adj[neighbour]) < parentDegree:\n",
    "                    parent = neighbour\n",
    "                    parentDegree = len(adj[neighbour])\n",
    "            # 检测 neighbours 是否为 adj[parent] 的子集\n",
    "            if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):\n",
    "                return 0\n",
    "\n",
    "            if parentDegree == currDegree:\n",
    "                ans = 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "\n",
    "        for a, b in pairs:\n",
    "            adj[a].add(b)\n",
    "            adj[b].add(a)\n",
    "\n",
    "        n = len(adj)\n",
    "\n",
    "        root = None\n",
    "        for k, v in adj.items():\n",
    "            if len(v) == n - 1:\n",
    "                root = k\n",
    "                break\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        ret = 1\n",
    "        for x in adj:\n",
    "            if x == root:\n",
    "                continue\n",
    "\n",
    "            fa = None\n",
    "            fad = inf\n",
    "            for y in adj[x]:\n",
    "                if len(adj[y]) >= len(adj[x]):\n",
    "                    if len(adj[y]) < fad:\n",
    "                        fad = len(adj[y])\n",
    "                        fa = y\n",
    "\n",
    "            if fa is None:\n",
    "                return 0\n",
    "\n",
    "\n",
    "            for y in adj[x]:\n",
    "                if y != fa and y not in adj[fa]:\n",
    "                    return 0\n",
    "\n",
    "            if len(adj[x]) == len(adj[fa]):\n",
    "                ret = 2\n",
    "\n",
    "        return ret\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "            1. 根节点是所有其余节点的祖先，可以和所有其他节点构成节点对，degree[root] = n - 1。\n",
    "            2. 如果 x 是 y 的祖先，那么一定有 degree[x] >= degree[y] 且 adj[y] 是 adj[x] 的子集。\n",
    "            3. 如果 x 是 y 的祖先，且 degree[x] = degree[y] 和 adj[x] = adj[y]，那么从 x 到 y 途径的所有节点都只有一个孩子节点。x 和 y 可以相互交换而不影响树的结构，此时构成方案不唯一。\n",
    "\n",
    "            - 如果 degree[x] > degree[y]，那么 x 是 y 的祖先节点。\n",
    "            - 如果 degree[x] < degree[y]，那么 y 是 x 的祖先节点。\n",
    "            - 如果 degree[x] = degree[y]，可能存在多种构造方法\n",
    "        \"\"\"\n",
    "        # 邻接表\n",
    "        adj = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "        n = len(adj)\n",
    "\n",
    "        # 寻找根节点\n",
    "        root = -1\n",
    "        for node, neighbours in adj.items():\n",
    "            if len(neighbours) == n - 1:\n",
    "                root = node\n",
    "        if root == -1:\n",
    "            return 0\n",
    "\n",
    "        # 根节点\n",
    "        res = 1\n",
    "\n",
    "        # 遍历每个节点\n",
    "        for node, neighbours in adj.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "            \n",
    "            curr_degree = len(neighbours)\n",
    "            parent = -1\n",
    "            parent_degree = n\n",
    "\n",
    "            # 根据 degree 大小找 node 的 parent 节点\n",
    "            for neighbour in neighbours:\n",
    "                if curr_degree <= len(adj[neighbour]) < parent_degree:\n",
    "                    parent = neighbour\n",
    "                    parent_degree = len(adj[neighbour])\n",
    "            \n",
    "            # 检查 neighbours 是否为 adj[parent] 的子集\n",
    "            if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):\n",
    "                return 0\n",
    "            \n",
    "            if parent_degree == curr_degree:\n",
    "                res = 2\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "\n",
    "        # 检测是否存在根节点\n",
    "        root = next((node for node, neighbours in adj.items() if len(neighbours) == len(adj) - 1), -1)\n",
    "        if root == -1:\n",
    "            return 0\n",
    "\n",
    "        ans = 1\n",
    "        for node, neighbours in adj.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            currDegree = len(neighbours)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 根据 degree 的大小找到 node 的父节点 parent\n",
    "            for neighbour in neighbours:\n",
    "                if currDegree <= len(adj[neighbour]) < parentDegree:\n",
    "                    parent = neighbour\n",
    "                    parentDegree = len(adj[neighbour])\n",
    "            # 检测 neighbours 是否为 adj[parent] 的子集\n",
    "            if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):\n",
    "                return 0\n",
    "\n",
    "            if parentDegree == currDegree:\n",
    "                ans = 2\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        domain = collections.defaultdict(set)\n",
    "        d = collections.defaultdict(int)\n",
    "        for u, v in pairs:\n",
    "            d[u] += 1\n",
    "            d[v] += 1\n",
    "            domain[u].add(v)\n",
    "            domain[v].add(u)\n",
    "        for u in d.keys():\n",
    "            domain[u].add(u)\n",
    "        # print(d)\n",
    "        # print(domain)\n",
    "        if max(d.values()) < len(d.values()) - 1:\n",
    "            return 0\n",
    "        f = 0\n",
    "        for u in d.keys():\n",
    "            for v in domain[u]:\n",
    "                if u == v:\n",
    "                    continue\n",
    "                if d[v] < d[u]:\n",
    "                    if domain[v] - domain[u]:\n",
    "                        return 0\n",
    "                if d[v] == d[u]:\n",
    "                    if domain[v] - domain[u]:\n",
    "                        return 0\n",
    "                    else:\n",
    "                        f = 1\n",
    "        if f:\n",
    "            return 2\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "\n",
    "        # 检测是否存在根节点\n",
    "        root = next((node for node, neighbours in adj.items() if len(neighbours) == len(adj) - 1), -1)\n",
    "        if root == -1:\n",
    "            return 0\n",
    "\n",
    "        ans = 1\n",
    "        for node, neighbours in adj.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            currDegree = len(neighbours)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 根据 degree 的大小找到 node 的父节点 parent\n",
    "            for neighbour in neighbours:\n",
    "                if currDegree <= len(adj[neighbour]) < parentDegree:\n",
    "                    parent = neighbour\n",
    "                    parentDegree = len(adj[neighbour])\n",
    "            # 检测 neighbours 是否为 adj[parent] 的子集\n",
    "            if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):\n",
    "                return 0\n",
    "\n",
    "            if parentDegree == currDegree:\n",
    "                ans = 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "\n",
    "        # 检测是否存在根节点\n",
    "        root = next((node for node, neighbours in adj.items() if len(neighbours) == len(adj) - 1), -1)\n",
    "        if root == -1:\n",
    "            return 0\n",
    "\n",
    "        ans = 1\n",
    "        for node, neighbours in adj.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            currDegree = len(neighbours)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 根据 degree 的大小找到 node 的父节点 parent\n",
    "            for neighbour in neighbours:\n",
    "                if currDegree <= len(adj[neighbour]) < parentDegree:\n",
    "                    parent = neighbour\n",
    "                    parentDegree = len(adj[neighbour])\n",
    "            # 检测 neighbours 是否为 adj[parent] 的子集\n",
    "            if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):\n",
    "                return 0\n",
    "\n",
    "            if parentDegree == currDegree:\n",
    "                ans = 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "\n",
    "        # 检测是否存在根节点\n",
    "        root = next((node for node, neighbours in adj.items() if len(neighbours) == len(adj) - 1), -1)\n",
    "        if root == -1:\n",
    "            return 0\n",
    "\n",
    "        ans = 1\n",
    "        for node, neighbours in adj.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            currDegree = len(neighbours)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 根据 degree 的大小找到 node 的父节点 parent\n",
    "            for neighbour in neighbours:\n",
    "                if currDegree <= len(adj[neighbour]) < parentDegree:\n",
    "                    parent = neighbour\n",
    "                    parentDegree = len(adj[neighbour])\n",
    "            # 检测 neighbours 是否为 adj[parent] 的子集\n",
    "            if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):\n",
    "                return 0\n",
    "\n",
    "            if parentDegree == currDegree:\n",
    "                ans = 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "\n",
    "        # 检测是否存在根节点\n",
    "        root = next((node for node, neighbours in adj.items() if len(neighbours) == len(adj) - 1), -1)\n",
    "        if root == -1:\n",
    "            return 0\n",
    "\n",
    "        ans = 1\n",
    "        for node, neighbours in adj.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            currDegree = len(neighbours)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 根据 degree 的大小找到 node 的父节点 parent\n",
    "            for neighbour in neighbours:\n",
    "                if currDegree <= len(adj[neighbour]) < parentDegree:\n",
    "                    parent = neighbour\n",
    "                    parentDegree = len(adj[neighbour])\n",
    "            # 检测 neighbours 是否为 adj[parent] 的子集\n",
    "            if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):\n",
    "                return 0\n",
    "\n",
    "            if parentDegree == currDegree:\n",
    "                ans = 2\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        graph = defaultdict(set)\n",
    "        for a, b in pairs:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "        n = len(graph)\n",
    "\n",
    "        ans = 1\n",
    "        roots = set()\n",
    "        for k, v in graph.items():\n",
    "            if len(v) == n - 1:\n",
    "                roots.add(k)\n",
    "            \n",
    "        # 没有可以作为根节点的点\n",
    "        if not roots:\n",
    "            return 0\n",
    "        \n",
    "        # 存在可以交换的根节点\n",
    "        if len(roots) > 1:\n",
    "            ans = 2\n",
    "\n",
    "        # 删掉所有根节点的关系，便于统计子树的根节点\n",
    "        for r in roots:\n",
    "            for other in graph[r] - roots:\n",
    "                graph[other] -= roots\n",
    "                if not graph[other]:\n",
    "                    graph.pop(other)\n",
    "            graph.pop(r)\n",
    "        \n",
    "        # 递归\n",
    "        def dfs(node):\n",
    "            res = 1\n",
    "            d = len(graph[node])\n",
    "            # 统计和子树度数一致的关系点\n",
    "            commons = {node}\n",
    "            for other in graph[node]:\n",
    "                if len(graph[other]) == d and len(graph[other] - graph[node]) == 1:\n",
    "                    res = 2\n",
    "                    commons.add(other)\n",
    "                    graph.pop(other)\n",
    "            # 删掉所有子树根节点\n",
    "            for other in graph[node]:\n",
    "                graph[other] -= commons\n",
    "            # 检查是否存在不在子树里的点却和子树的节点有关系\n",
    "            for block in graph.keys() - graph[node] - commons:\n",
    "                if graph[block] & graph[node]:\n",
    "                    return 0\n",
    "            graph.pop(node)\n",
    "            return res\n",
    "        \n",
    "        while graph:\n",
    "            # 找子节点最多的节点\n",
    "            node = max(graph.keys(), key=lambda x:len(graph[x]))\n",
    "            ans *= dfs(node)\n",
    "            if not ans:\n",
    "                return 0\n",
    "\n",
    "        return 2 if ans > 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "            1. 根节点是所有其余节点的祖先，可以和所有其他节点构成节点对，degree[root] = n - 1。\n",
    "            2. 如果 x 是 y 的祖先，那么一定有 degree[x] >= degree[y] 且 adj[y] 是 adj[x] 的子集。\n",
    "            3. 如果 x 是 y 的祖先，且 degree[x] = degree[y] 和 adj[x] = adj[y]，那么从 x 到 y 途径的所有节点都只有一个孩子节点。x 和 y 可以相互交换而不影响树的结构，此时构成方案不唯一。\n",
    "\n",
    "            - 如果 degree[x] > degree[y]，那么 x 是 y 的祖先节点。\n",
    "            - 如果 degree[x] < degree[y]，那么 y 是 x 的祖先节点。\n",
    "            - 如果 degree[x] = degree[y]，可能存在多种构造方法\n",
    "\n",
    "            1's parent is 2\n",
    "            3's parent is 2\n",
    "\n",
    "            1's parent is 2\n",
    "            2's parent is 1\n",
    "        \"\"\"\n",
    "        # 邻接表\n",
    "        adj = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "        n = len(adj)\n",
    "\n",
    "        # 寻找根节点\n",
    "        root = -1\n",
    "        for node, neighbours in adj.items():\n",
    "            if len(neighbours) == n - 1:\n",
    "                root = node\n",
    "\n",
    "        # 找不到根节点\n",
    "        if root == -1:\n",
    "            return 0\n",
    "\n",
    "        # 根节点\n",
    "        res = 1\n",
    "\n",
    "        # 遍历每个节点\n",
    "        for node, neighbours in adj.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "            \n",
    "            curr_degree = len(neighbours)\n",
    "            parent = -1\n",
    "            parent_degree = n\n",
    "\n",
    "            # 根据 degree 大小找 node 的 parent 节点\n",
    "            for neighbour in neighbours:\n",
    "                if curr_degree <= len(adj[neighbour]) < parent_degree:\n",
    "                    parent = neighbour\n",
    "                    parent_degree = len(adj[neighbour])\n",
    "            \n",
    "            # 检查 neighbours 是否为 adj[parent] 的子集\n",
    "            if parent == -1:\n",
    "                return 0\n",
    "\n",
    "            for neighbour in neighbours:\n",
    "                if neighbour != parent and neighbour not in adj[parent]:\n",
    "                    return 0\n",
    "            \n",
    "            if parent_degree == curr_degree:\n",
    "                res = 2\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "\n",
    "        # 检测是否存在根节点\n",
    "        root = next((node for node, neighbours in adj.items() if len(neighbours) == len(adj) - 1), -1)\n",
    "        if root == -1:\n",
    "            return 0\n",
    "\n",
    "        ans = 1\n",
    "        for node, neighbours in adj.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            currDegree = len(neighbours)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 根据 degree 的大小找到 node 的父节点 parent\n",
    "            for neighbour in neighbours:\n",
    "                if currDegree <= len(adj[neighbour]) < parentDegree:\n",
    "                    parent = neighbour\n",
    "                    parentDegree = len(adj[neighbour])\n",
    "            # 检测 neighbours 是否为 adj[parent] 的子集\n",
    "            if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):\n",
    "                return 0\n",
    "\n",
    "            if parentDegree == currDegree:\n",
    "                ans = 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        neighbors = collections.defaultdict(set)\n",
    "        degree = collections.defaultdict(int)\n",
    "        for a, b in pairs:\n",
    "            degree[a] += 1\n",
    "            degree[b] += 1\n",
    "            neighbors[a].add(b)\n",
    "            neighbors[b].add(a)\n",
    "\n",
    "        n = len(degree)\n",
    "        if max(degree.values()) < n - 1:\n",
    "            return 0\n",
    "\n",
    "        has_dup = False\n",
    "        for cur, d in degree.items():\n",
    "            p, pd = -1, n\n",
    "            for nxt in neighbors[cur]:\n",
    "                if degree[nxt] >= degree[cur] and degree[nxt] < pd:\n",
    "                    p, pd = nxt, degree[nxt]\n",
    "            if pd == degree[cur]:\n",
    "                has_dup = True\n",
    "            if d == n - 1:\n",
    "                continue\n",
    "            if p == -1:\n",
    "                return 0\n",
    "            for a in neighbors[cur]:\n",
    "                if a != p and a not in neighbors[p]:\n",
    "                    return 0\n",
    "        return 2 if has_dup else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for x, y in pairs:\n",
    "            adj[x].add(y)\n",
    "            adj[y].add(x)\n",
    "\n",
    "        # 检测是否存在根节点\n",
    "        root = next((node for node, neighbours in adj.items() if len(neighbours) == len(adj) - 1), -1)\n",
    "        if root == -1:\n",
    "            return 0\n",
    "\n",
    "        ans = 1\n",
    "        for node, neighbours in adj.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            currDegree = len(neighbours)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 根据 degree 的大小找到 node 的父节点 parent\n",
    "            for neighbour in neighbours:\n",
    "                if currDegree <= len(adj[neighbour]) < parentDegree:\n",
    "                    parent = neighbour\n",
    "                    parentDegree = len(adj[neighbour])\n",
    "            # 检测 neighbours 是否为 adj[parent] 的子集\n",
    "            if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):\n",
    "                return 0\n",
    "\n",
    "            if parentDegree == currDegree:\n",
    "                ans = 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        d = defaultdict(set)\n",
    "        for i, j in pairs:\n",
    "            d[i].add(j)\n",
    "            d[j].add(i)\n",
    "\n",
    "        # 检测是否有根节点\n",
    "        root = -1\n",
    "        for i, neighbors in d.items():\n",
    "            if len(neighbors) == len(d) - 1:\n",
    "                root = i\n",
    "                break\n",
    "        if root == -1:\n",
    "            return 0\n",
    "        ans = 1\n",
    "        for node, neighbors in d.items():\n",
    "            if node == root:\n",
    "                continue\n",
    "\n",
    "            nowDegree = len(neighbors)\n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            # 寻找node的父节点\n",
    "            for neighbor in neighbors:\n",
    "                if nowDegree <= len(d[neighbor]) < parentDegree:\n",
    "                    parent = neighbor\n",
    "                    parentDegree = len(d[neighbor])\n",
    "            if parent == -1 or any(neighbor != parent and neighbor not in d[parent] for neighbor in neighbors):\n",
    "                return 0\n",
    "            if parentDegree == nowDegree:\n",
    "                ans = 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        graph = defaultdict(set)\n",
    "        for f,t in pairs:\n",
    "            graph[f].add(t)\n",
    "            graph[t].add(f)\n",
    "\n",
    "\n",
    "        # 检测是否存在根节点\n",
    "        root = next((node for node in graph if len(graph[node])==len(graph)-1), -1)\n",
    "        ret = 1\n",
    "        if root == -1:\n",
    "            return 0\n",
    "        for node in graph:\n",
    "            if node==root:\n",
    "                continue \n",
    "            parent = -1\n",
    "            parentDegree = maxsize\n",
    "            for n in graph[node]:\n",
    "                if len(graph[node])<=len(graph[n])<parentDegree:\n",
    "                    parent = n \n",
    "                    parentDegree = len(graph[n])\n",
    "\n",
    "            if parent<0 or any(n!=parent and n not in graph[parent]  for n in graph[node]):\n",
    "                # print(node,parent)\n",
    "                return 0 \n",
    "            # print(node,parent)\n",
    "            if len(graph[parent])==len(graph[node]):\n",
    "                print(parent,node)\n",
    "                ret = 2\n",
    "        return ret \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        graph = defaultdict(set)\n",
    "        for a, b in pairs:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "        n = len(graph)\n",
    "\n",
    "        ans = 1\n",
    "        roots = set()\n",
    "        for k, v in graph.items():\n",
    "            if len(v) == n - 1:\n",
    "                roots.add(k)\n",
    "            \n",
    "        # 没有可以作为根节点的点\n",
    "        if not roots:\n",
    "            return 0\n",
    "        \n",
    "        # 存在可以交换的根节点\n",
    "        if len(roots) > 1:\n",
    "            ans = 2\n",
    "\n",
    "        # 删掉所有根节点的关系，便于统计子树的根节点\n",
    "        for r in roots:\n",
    "            for other in graph[r] - roots:\n",
    "                graph[other] -= roots\n",
    "                if not graph[other]:\n",
    "                    graph.pop(other)\n",
    "            graph.pop(r)\n",
    "        \n",
    "        # 递归\n",
    "        def dfs(node):\n",
    "            res = 1\n",
    "            d = len(graph[node])\n",
    "            # 统计和子树度数一致的关系点\n",
    "            commons = {node}\n",
    "            for other in graph[node]:\n",
    "                if len(graph[other]) == d and len(graph[other] - graph[node]) == 1:\n",
    "                    res = 2\n",
    "                    commons.add(other)\n",
    "                    graph.pop(other)\n",
    "            # 删掉所有子树根节点\n",
    "            for other in graph[node]:\n",
    "                graph[other] -= commons\n",
    "            # 检查是否存在不在子树里的点却和子树的节点有关系\n",
    "            for block in graph.keys() - graph[node] - commons:\n",
    "                if graph[block] & graph[node]:\n",
    "                    return 0\n",
    "            graph.pop(node)\n",
    "            return res\n",
    "        \n",
    "        while graph:\n",
    "            # 找子节点最多的节点\n",
    "            node = max(graph.keys(), key=lambda x:len(graph[x]))\n",
    "            ans *= dfs(node)\n",
    "            if not ans:\n",
    "                return 0\n",
    "\n",
    "        return 2 if ans > 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkWays(self, pairs: List[List[int]]) -> int:\n",
    "        neighbors = collections.defaultdict(set)\n",
    "        for a, b in pairs:\n",
    "            neighbors[a].add(b)\n",
    "            neighbors[b].add(a)\n",
    "\n",
    "        n = len(neighbors)\n",
    "        if max([len(l) for l in neighbors.values()]) < n - 1:\n",
    "            return 0\n",
    "\n",
    "        has_dup = False\n",
    "        for a, la in neighbors.items():\n",
    "            p, pd = -1, math.inf\n",
    "            for b in la:\n",
    "                d = len(neighbors[b])\n",
    "                if d >= len(la) and d < pd:\n",
    "                    p, pd = b, d\n",
    "            if len(la) == pd:\n",
    "                has_dup = True\n",
    "            if len(la) == n - 1:\n",
    "                continue\n",
    "            if p == -1:\n",
    "                return 0\n",
    "            for x in la:\n",
    "                if x != p and x not in neighbors[p]:\n",
    "                    return 0\n",
    "\n",
    "        return 2 if has_dup else 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
